package 剑指专题.二叉树;


/*
 * Author：江松
 * Date：2023/3/25 10:13
 *
 二叉搜索树的后序遍历序列
 1，分治：划分区间L，R，root；根就是最后一个点，
 左区间比根小，右区间比根大，
 根据左区间进行划分（严格小于根），若右区间出现比右区间小的那就不合法

 2,单调栈：倒序就是，根--R--L，
 这样就会是升序，一旦出现降序，说明进入了左子树，
 那么这个---从下降点往前找到比他大且最接近于他的点---就是左子树的根节点；
 既然是左子树根节点，那么应该大于左子树节点，
 如果逆序遍历中出现相反情况，说明不是二叉搜索树
 */


import java.util.Stack;

public class Main7 {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length==0)return false;
        int root=Integer.MAX_VALUE;
        Stack<Integer>stack=new Stack<>();
        for(int i=sequence.length-1;i>=0;--i){
            if(sequence[i]>root)return false;
            while (!stack.isEmpty()&&sequence[i]<stack.peek()){
                root=stack.peek();
                stack.pop();
            }
            stack.push(sequence[i]);
        }
        return true;
    }
    /*
    public boolean check(int []a,int l,int r){
        if(l>=r)return true;
        int root=a[r];
        //划分，右区间的开始
        int rst=l;
        while(a[rst]<root){
            rst++;
        }
        //比较右区间和根
        for(int i=rst;i<r;++i){
            if(a[i]<root)return false;
        }
        //分治
        return check(a,l,rst-1)&&check(a,rst,r-1);
    }
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length==0)return false;
        return check(sequence,0,sequence.length-1);
    }
    */
}
